home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _transclosure.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  3.7 KB  |  182 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _transclosure.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  TRANSITIVE_CLOSURE (transitive closure)                                     *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23. #include <LEDA/graph_alg.h>
  24.  
  25. typedef list<node>* nodelist_ptr;
  26.  
  27.  
  28.  
  29.  
  30. static void acyclic_transitive_closure(graph& G)
  31. { // computes transitive closure of acyclic graph G
  32.  
  33. node v,w;
  34.  
  35. int i,j,k,h;
  36. int n = G.number_of_nodes();
  37.  
  38. TOPSORT1(G); 
  39.  
  40. node_array<int> marked(G);
  41. node_array<int> top_ord(G);   // topologic order
  42. node_array<int> chain(G);     // chain[v] = i  iff  v in C[i]
  43.  
  44. node_list* C = new node_list[n+1];  // chains C[0], C[1], ...
  45.  
  46. node*      N = new node[n];         // N[i] = i-th node in topological order
  47.  
  48. int**      reach = new int*[n];     // reach[h][i] = min { j ; N[j] in C[h] and
  49.                                     // there is a path from N[i] to N[j] }
  50.  
  51.  
  52. for(i=0; i<n; i++) reach[i] = new int[n];
  53.  
  54. i=0;
  55. forall_nodes(v,G) { marked[v]=1; top_ord[v] = i; N[i]=v; i++; }
  56.  
  57. // compute chain decomposition C[0], C[1], ..., C[k]
  58.  
  59. k=0;
  60. forall_nodes(v,G) 
  61.  { node v0 = v;
  62.    if (marked[v0])
  63.     {  C[k].append(v0);  
  64.        chain[v0]=k;
  65.        while (v0 != nil)
  66.        { node u = nil;
  67.          forall_adj_nodes(w,v0) 
  68.            if (marked[w]) 
  69.            {  u = w;
  70.               break; 
  71.             }
  72.  
  73.          if (u != nil) 
  74.          { marked[u]=0;
  75.            chain[u]=k;
  76.            C[k].append(u);
  77.           }
  78.          v0=u;
  79.         }
  80.        k++;
  81.     }
  82.   }
  83. k--;
  84.  
  85.  
  86. for(h=0; h<n; h++)
  87.   for(i=0; i<n; i++)
  88.     reach[h][i] = n+1;
  89.  
  90. Forall_nodes(v,G)       //decreasing order
  91. { i=top_ord[v];
  92.   forall_adj_nodes(w,v) //increasing order
  93.   { j=top_ord[w];
  94.     if (j <= reach[chain[w]][j])
  95.      for(h=0; h<=k; h++)
  96.        if (reach[h][j] < reach[h][i]) reach[h][i] = reach[h][j];
  97.   }
  98.   reach[chain[v]][i] = i;
  99. }
  100.  
  101.  
  102. G.del_all_edges();
  103.  
  104. forall_nodes(v,G)
  105.   for(i=0; i<=k; i++)
  106.     { j = reach[i][top_ord[v]];
  107.       if ( j < n+1 )
  108.         for(w = N[j]; w != nil; w = C[i].succ(w)) G.new_edge(v,w);
  109.      }
  110.  
  111.  
  112. for(i=0; i<=k; i++) C[i].clear();
  113. delete[] C;
  114.  
  115. for(i=0; i<n; i++) delete reach[i];
  116. delete reach;
  117.  
  118. delete N;
  119.  
  120. }
  121.  
  122.  
  123. graph TRANSITIVE_CLOSURE(const graph& G0)
  124. {
  125.   node v,w;
  126.   edge e;
  127.   int i,j;
  128.  
  129.   graph G = G0;
  130.  
  131.   node_array<int> compnum(G);
  132.   int k = STRONG_COMPONENTS(G,compnum);
  133.  
  134. /* reduce graph G to graph G1 = (V',E') 
  135.    with V' = { V[0],V[1],...,V[k] } = set of scc's of G
  136.    and (V[i],V[j]) in E' iff there is an edge from V[i] to V[j] in G
  137.  
  138.    G1.inf(V[i]) = set of nodes v in G with v in scc i (i.e. compum[v] = i)
  139. */
  140.  
  141.   GRAPH<nodelist_ptr,int> G1;
  142.  
  143.   node*  V = new node[k];
  144.  
  145.   for(j=0; j < k; j++) V[j] = G1.new_node(new list<node>);
  146.  
  147.   forall_nodes(v,G) 
  148.   { int i = compnum[v];
  149.     G1[V[i]]->append(v);
  150.    }
  151.   
  152.   forall_edges(e,G)
  153.   { i = compnum[source(e)];
  154.     j = compnum[target(e)];
  155.     if (i!=j) G1.new_edge(V[i],V[j]);
  156.    }
  157.  
  158.   eliminate_parallel_edges(G1);
  159.   
  160.   // compute transitive closure of acyclic graph G1
  161.  
  162.   acyclic_transitive_closure(G1);
  163.  
  164.   G.del_all_edges();
  165.   
  166.   list_item x,y;
  167.  
  168.   forall_nodes(v,G1)
  169.   { list<node>* plv = G1[v];
  170.     forall_adj_nodes(w,v)
  171.        forall_items(x,*plv)
  172.           forall_items(y,*(G1[w])) G.new_edge(plv->inf(x),G1[w]->inf(y));
  173.    }
  174.   
  175.    forall_nodes(v,G1) delete G1[v];
  176.   
  177.    delete V;
  178.  
  179.    return G;
  180. }
  181.  
  182.